1. Field of the Invention
The invention relates to path planning and in particular to repropagating cost waves in a configuration space after some aspect of that space has been changed.
The invention also relates to path planning in a configuration space in which the location of obstacles is not known.
2. Prior Art
The field of path planning is one with many applications. The most common application is to controlling robots, for instance robot arms such as are used in the space shuttle. Other applications include electronic maps, traffic control, emergency vehicle control, and emergency exit systems.
The path planning problem, as applied to robots, typically involves getting a robot from a start point to a goal point while avoiding obstacles. Automating multi-dimensional path planning for robots is one of the great historical problems of robotics.
The present invention is an improvement on the invention disclosed U.S. patent application Ser. No. 123,502, which is incorporated herein by reference as background material. That application disclosed, amongst other things, propagating cost waves through a configuration space by budding, using a space-variant metric.
After budding, some aspect of the configuration space may change, for instance, if an obstacle is removed or a goal added. In such a case, it may be inefficient to bud the entire configuration space again because only a small part of the configuration space may be affected.
Another problem which arises after a change in configuration space is that the precise location of the changes, particularly in obstacle location, may not be known. An approach to this problem is set forth in V. Lumelsky, "Algorithmic and Complexity Issues of Robot Motion in an Uncertain Environment", Journal of Complexity 3, 146-182 (1987); and V. Lumelsky, "Dynamic Path Planning for a Planar Articulated Robot Arm Moving Amidst Unknown Obstacles", Automatica, Vol. 23., No. 5, pp. 551-570 (1987). This approach suffers from certain shortcomings. For instance, the method disclosed is only able to deal with two dimensions. The method also does not have a memory for previously encountered obstacles.